Data often contains redundancy in the form of repeated patterns in a data frame, such as repeated bits, repeated bytes, repeated strings of bits and repeated strings of bytes. Compression represents frequently repeated data patterns in shorter binary codes thus reducing the total number of bits used to send out the entire data frame. For example, the letter “e” appears most frequently in an English context, so the letter “e” is represented by one dot in Morse code for transmission efficiency.
Data compression techniques aim to identify such repeated data patterns and then replace them with shorter strings. Many data compression techniques rely on one or more search engines to find such redundancy. There is a tradeoff between compression efficiency and the size of the search engines. Generally, larger search engines exhibit better compression efficiency, but also bring larger area and power consumption requirements for a hardware implementation, as well as longer latency in performing the search.
For a given search engine with a predefined boundary or a target engine with a smaller boundary size, a need exists for improved data compression techniques that remove redundancy across the boundary of compression search engines.